This notebook presents the different synthetic experiments exhibited in the associated paper, and provides examples for using the functions and distances developed throughout this project. All of the following has been implemented in R and heavily relies on exterior libraries (igraph and nettools).

0. Loading packages and functions

Start by loading all the different functions.

## [1] "Working directory set to /Users/cdonnat/Dropbox/TrackingNetworkChanges/tests_synthetic_data"
## 
## Attaching package: 'gplots'
## The following object is masked from 'package:stats':
## 
##     lowess
## 
## 
## Attaching package: 'igraph'
## The following objects are masked from 'package:stats':
## 
##     decompose, spectrum
## The following object is masked from 'package:base':
## 
##     union
## Warning: package 'Matrix' was built under R version 3.3.2
## Loading required package: MASS
## 
## Attaching package: 'MASS'
## The following object is masked _by_ '.GlobalEnv':
## 
##     ginv
## Loading required package: statnet.common
## Loading required package: network
## network: Classes for Relational Data
## Version 1.13.0 created on 2015-08-31.
## copyright (c) 2005, Carter T. Butts, University of California-Irvine
##                     Mark S. Handcock, University of California -- Los Angeles
##                     David R. Hunter, Penn State University
##                     Martina Morris, University of Washington
##                     Skye Bender-deMoll, University of Washington
##  For citation information, type citation("network").
##  Type help("network-package") to get started.
## 
## Attaching package: 'network'
## The following objects are masked from 'package:igraph':
## 
##     %c%, %s%, add.edges, add.vertices, delete.edges,
##     delete.vertices, get.edge.attribute, get.edges,
##     get.vertex.attribute, is.bipartite, is.directed,
##     list.edge.attributes, list.vertex.attributes,
##     set.edge.attribute, set.vertex.attribute
## sna: Tools for Social Network Analysis
## Version 2.4 created on 2016-07-23.
## copyright (c) 2005, Carter T. Butts, University of California-Irvine
##  For citation information, type citation("sna").
##  Type help(package="sna") to get started.
## 
## Attaching package: 'sna'
## The following objects are masked from 'package:igraph':
## 
##     betweenness, bonpow, closeness, components, degree,
##     dyad.census, evcent, hierarchy, is.connected, neighborhood,
##     triad.census
## [1] "All functions loaded."

I. Random Graph generation

Here we try generating different instances of random graphs. Indeed, if the Erdos-Renyi random graph often appears to be one of the simplest and most natural random graph to generate, numerous works throughout the literature have underlined its limitations when it comes to reproducing “real life graphs”. This is why we propose to enrich our synthetic graph library (for our experiments) by synthetizing other types of random structures that have been argued to be more realsitic: the Power Law graph (Barabasi-Albert model), an Island graph, a dot product graph and an SBM graph. All of the R igraph generation functions for these graphs have been wrapped in the same function (generate_realistic_adjacency), and the following code snipppets show how to generate a variety of such different graphs.

N=50
Adj=generate_realistic_adjacency(N,opts=0,args=list(),verbose=TRUE,p=0.16)
## [1] "Type of graph generated:  ER"

generate_realistic_adjacency(N,opts=1,args=list(),verbose=TRUE,pow= 2.4)
## [1] "Type of graph generated:  Power Law"
## [1] "power graph: p= 2.4"

## IGRAPH U--- 50 49 -- Barabasi graph
## + attr: name (g/c), power (g/n), m (g/n), zero.appeal (g/n),
## | algorithm (g/c)
## + edges:
##  [1]  1-- 2  1-- 3  3-- 4  2-- 5  1-- 6  5-- 7  2-- 8  2-- 9  1--10  9--11
## [11]  1--12  1--13  1--14 10--15  1--16  1--17 14--18  1--19  1--20  2--21
## [21]  2--22  1--23  5--24  1--25  5--26 24--27  1--28  1--29  1--30  1--31
## [31]  1--32  1--33 24--34  1--35  1--36  1--37  1--38  1--39  1--40  1--41
## [41]  1--42  1--43  1--44  1--45  1--46  1--47  1--48  1--49  1--50
G=generate_realistic_adjacency(N,opts=2,args=list(),verbose=TRUE,islands.n=4,islands.size=18,islands.pin=0.2,n.inter=7)
## [1] "Type of graph generated:  Island"
## [1] "island graph: islands.n= 4 18"

G=generate_realistic_adjacency(N,opts=3,args=list(),verbose=TRUE,K=10)
## [1] "Type of graph generated:  Dot Product"
## [1] "dot product graph"

G=generate_realistic_adjacency(N,opts=4,args=list(),verbose=TRUE,pm=cbind( c(0.4,0.1, 0.001), c(.1,0.2, .01),c(.001,0.01, .5)))
## [1] "Type of graph generated:  SBM"
## [1] 50
## [1] "stochastic block model: block size 10"
## [2] "stochastic block model: block size 10"
## [3] "stochastic block model: block size 10"

II. Generate smooth evolution process

N=70
p0=0.15
p=0.5
p_disp=0.3
p_creation=0.01
prop=0.3
dist_smooth=test_smooth_RD_changes(N,p0,p,p_disp,p_creation,prop,T=11,alphas=c(0.1,0.4,0.9,1.2,3),verbose=TRUE, go_plot=TRUE,initial_message=TRUE,save_graph_seq=T, name_file_ext="",path_to_graph='/Users/cdonnat/Dropbox/TrackingNetworkChanges/tests_synthetic_data/generated_graphs/',name_graph='ER_70nodes',path2plot='/Users/cdonnat/Dropbox/TrackingNetworkChanges/tests_synthetic_data/plots_experiments/')
## [1] "Investigating the distance for evolution of a graph over time with random changes:"
## [1] "At each time iteration,  30 % of nodes are randomly reassigned (ER-model)"
## [1] "time:  1"
## [1] "time:  2"
## [1] "time:  3"
## [1] "time:  4"
## [1] "time:  5"
## [1] "time:  6"
## [1] "time:  7"
## [1] "time:  8"
## [1] "time:  9"
## [1] "time:  10"

Try the previous for different types of topology.

N=70

m=10
p_modified=0.6
dist_smooth_PA=test_smooth_Realistic_changes(N,m,m_disp=0,m_creation=0, p_modified, p_disp=0.3,p_creation=0.01,T=11,opts=1,alphas=c(0.1,0.4,0.9,1.2,3),verbose=FALSE,go_plot=TRUE,initial_message=TRUE,save_graph_seq=TRUE,path_to_graph='./tests_synthetic_data/generated_graphs/', name_file_ext="",very_verbose=F,path2plots='./tests_synthetic_data/plots_experiments/')
## [1] "Type of graph generated:  Power Law"
## [1] "power graph: p= 0.9"

## [1] "Investigating the distance for evolution of a graph over time with random changes:"
## [1] "A graph with N= 70 nodes is considered as per creation model  1"
## [1] "At each time iteration,  10 edges are either randomly reassigned or disppear with proba  0.3"
## [1] "Probablity of creation a a new edge for each vertex=  0.01"

III. Generate evolution process with change point

test_ER_changepoint=test_change_point(N=30,p0=0.4,p=0.4,prop=0.05,prop2=0.2,p2=0.4, T=21,verbose=FALSE,go_plot=TRUE,initial_message=TRUE,save_graph_seq=TRUE)
## [1] "Investigating the ability of the distance to detect dynamic regime changes"
## [1] "An ER graph with N= 30 nodes is considered, with edge proba= 0.4"
## [1] "At time t=10, the proportion of nodes randomly reassigned changes from 0.05  to  0.2 with new connection proba=  0.4"

 print(test_ER_changepoint$dist) 
##                             X1           X2           X3           X4
## Hamming1          0.0137931034 0.0229885057 9.195402e-03 9.195402e-03
## Jaccard           0.0329670330 0.0543478261 2.209945e-02 2.209945e-02
## Spanning Trees    0.0005650071 0.0005380344 7.092209e-05 1.461629e-04
## Hamming           0.0137931034 0.0229885057 9.195402e-03 9.195402e-03
## IM                0.0050990063 0.0059547854 4.303080e-03 2.910588e-03
## HIM               0.0103983068 0.0167918264 7.178855e-03 6.820079e-03
## alpha=0.5,order=5 1.8086355288 2.8363843628 7.027526e-01 7.198609e-01
## alpha=0.5,order=3 0.0353790322 0.0610937531 2.171230e-02 2.390727e-02
## alpha=0.9,order=3 0.0207364615 0.0353391022 1.337782e-02 1.413481e-02
## ST norm           0.0002825035 0.0002690172 3.546104e-05 7.308143e-05
## f(l)=exp(-0.1l)   0.0420773410 0.0760503400 4.714775e-02 5.851008e-02
## f(l)=exp(-0.4l)   0.1683093640 0.3042013602 1.885910e-01 2.340403e-01
## f(l)=exp(-0.9l)   0.3786960689 0.6844530604 4.243297e-01 5.265907e-01
## f(l)=exp(-1.2l)   0.5049280919 0.9126040805 5.657729e-01 7.021209e-01
## f(l)=exp(-3l)     1.2623202296 2.2815102013 1.414432e+00 1.755302e+00
## f(l)= l. 1(l<2)   2.0276701509 1.9315035322 3.447996e-01 1.961351e+00
##                             X5           X6           X7           X8
## Hamming1          0.0137931034 0.0183908046 0.0229885057 9.195402e-03
## Jaccard           0.0329670330 0.0437158470 0.0543478261 2.209945e-02
## Spanning Trees    0.0002287726 0.0016196469 0.0018866355 7.374732e-05
## Hamming           0.0137931034 0.0183908046 0.0229885057 9.195402e-03
## IM                0.0030289791 0.0117711863 0.0118055760 2.424621e-03
## HIM               0.0099856001 0.0154399242 0.0182735194 6.724367e-03
## alpha=0.5,order=5 1.1485484352 2.0676988595 3.9995390267 8.037123e-01
## alpha=0.5,order=3 0.0334134136 0.0451099286 0.0638593307 2.299852e-02
## alpha=0.9,order=3 0.0203919664 0.0271594400 0.0356987484 1.380902e-02
## ST norm           0.0001143863 0.0008098233 0.0009433175 3.687366e-05
## f(l)=exp(-0.1l)   0.0501965765 0.0576680574 0.0867795319 5.654461e-02
## f(l)=exp(-0.4l)   0.2007863058 0.2306722295 0.3471181275 2.261784e-01
## f(l)=exp(-0.9l)   0.4517691882 0.5190125163 0.7810157868 5.089015e-01
## f(l)=exp(-1.2l)   0.6023589175 0.6920166884 1.0413543824 6.785353e-01
## f(l)=exp(-3l)     1.5058972938 1.7300417210 2.6033859560 1.696338e+00
## f(l)= l. 1(l<2)   2.0159083320 2.0076185518 0.6592748195 1.852103e+00
##                             X9         X10         X11          X12
## Hamming1          0.0183908046 0.059770115 0.059770115 0.0643678161
## Jaccard           0.0437158470 0.135416667 0.135416667 0.1450777202
## Spanning Trees    0.0003115891 0.004320910 0.002234138 0.0003530074
## Hamming           0.0183908046 0.059770115 0.059770115 0.0643678161
## IM                0.0066507974 0.024986453 0.015669006 0.0087018827
## HIM               0.0138284996 0.045808239 0.043692015 0.0459289588
## alpha=0.5,order=5 2.3197085497 9.935548694 6.592465758 7.4348561437
## alpha=0.5,order=3 0.0491864142 0.156912186 0.147293429 0.1673458867
## alpha=0.9,order=3 0.0283653723 0.090586237 0.088855953 0.0980276009
## ST norm           0.0001557946 0.002160451 0.001117068 0.0001765037
## f(l)=exp(-0.1l)   0.0579356670 0.074673910 0.086306765 0.0989843460
## f(l)=exp(-0.4l)   0.2317426681 0.298695638 0.345227061 0.3959373841
## f(l)=exp(-0.9l)   0.5214210033 0.672065186 0.776760886 0.8908591143
## f(l)=exp(-1.2l)   0.6952280044 0.896086914 1.035681182 1.1878121524
## f(l)=exp(-3l)     1.7380700110 2.240217286 2.589202955 2.9695303810
## f(l)= l. 1(l<2)   1.9408210537 2.005519590 0.334373181 1.9679705531
##                            X13          X14          X15         X16
## Hamming1           0.082758621 9.195402e-02  0.064367816 0.082758621
## Jaccard            0.182741117 2.010050e-01  0.145077720 0.182741117
## Spanning Trees     0.002166683 3.109118e-04  0.003275075 0.000908910
## Hamming            0.082758621 9.195402e-02  0.064367816 0.082758621
## IM                 0.013342831 1.177695e-02  0.027477700 0.010874034
## HIM                0.059274870 6.555242e-02  0.049488583 0.059022173
## alpha=0.5,order=5 12.168963126 1.429781e+01 10.929845386 8.283949521
## alpha=0.5,order=3  0.213619932 2.534295e-01  0.176021357 0.202518775
## alpha=0.9,order=3  0.124665262 1.433362e-01  0.099464562 0.122412459
## ST norm            0.001083341 1.554559e-04  0.001637536 0.000454455
## f(l)=exp(-0.1l)    0.115192408 8.395682e-02  0.101699444 0.109752346
## f(l)=exp(-0.4l)    0.460769633 3.358273e-01  0.406797778 0.439009382
## f(l)=exp(-0.9l)    1.036731674 7.556114e-01  0.915295000 0.987771110
## f(l)=exp(-1.2l)    1.382308899 1.007482e+00  1.220393333 1.317028147
## f(l)=exp(-3l)      3.455772246 2.518705e+00  3.050983332 3.292570367
## f(l)= l. 1(l<2)    2.697078141 1.893563e+00  2.016891313 2.060472040
##                            X17          X18          X19          X20
## Hamming1          0.0873563218  0.087356322  0.087356322  0.050574713
## Jaccard           0.1919191919  0.191919192  0.191919192  0.115789474
## Spanning Trees    0.0016170007  0.009540811  0.002916384  0.004394348
## Hamming           0.0873563218  0.087356322  0.087356322  0.050574713
## IM                0.0175216165  0.037721042  0.013475909  0.012097713
## HIM               0.0630005318  0.067282999  0.062500908  0.036770615
## alpha=0.5,order=5 8.4865922311 19.363411364 14.814828129 13.892341582
## alpha=0.5,order=3 0.2180839920  0.236943259  0.228711861  0.147647189
## alpha=0.9,order=3 0.1310541151  0.134364262  0.132914722  0.080124383
## ST norm           0.0008085002  0.004770369  0.001458191  0.002197171
## f(l)=exp(-0.1l)   0.0589431753  0.103897991  0.106500263  0.083821207
## f(l)=exp(-0.4l)   0.2357727011  0.415591966  0.426001052  0.335284829
## f(l)=exp(-0.9l)   0.5304885774  0.935081923  0.958502366  0.754390866
## f(l)=exp(-1.2l)   0.7073181033  1.246775897  1.278003155  1.005854488
## f(l)=exp(-3l)     1.7682952582  3.116939742  3.195007887  2.514636219
## f(l)= l. 1(l<2)   0.3407019986  0.547853471  2.836024608  2.063635733
change_pointPA=test_change_point_realistic(N=70,m=c(10,20),p_mod=c(0.6,0.2),p_disp=c(0.1,0.2),p_creation=c(0.0,0.0),opts=1, T=21,verbose=TRUE,m_disp=c(0,0,0),m_creation=c(2,5,0),go_plot=TRUE,initial_message=TRUE,very_verbose=FALSE,save_graph_seq=FALSE,name_file_ext="")
## [1] "Investigating the ability of the distance to detect dynamic regime changes"
## [1] "A graph with N= 70 nodes is considered as per creation model  1"
## [1] "At time t=10, the number of randomly reassigned edges changes from 10  to  20 with new change proba=  NA  vs  0.5 and deletion 0.2"
## [1] "Type of graph generated:  Power Law"
## [1] "power graph: p= 0.9"

## [1] "time:  1"
## [1] "time:  2"
## [1] "time:  3"
## [1] "time:  4"
## [1] "time:  5"
## [1] "time:  6"
## [1] "time:  7"
## [1] "time:  8"
## [1] "time:  9"
## [1] "time:  10"
## [1] "time:  11"
## [1] "time:  12"
## [1] "time:  13"
## [1] "time:  14"
## [1] "changed back"
## [1] "time:  15"
## [1] "changed back"
## [1] "time:  16"
## [1] "changed back"
## [1] "time:  17"
## [1] "changed back"
## [1] "time:  18"
## [1] "changed back"
## [1] "time:  19"
## [1] "changed back"
## [1] "time:  20"
## [1] "changed back"

print(change_pointPA$dist) 
##                            X1          X2         X3         X4         X5
## Hamming1          0.004140787 0.010766046 0.01325052 0.01076605 0.01159420
## Jaccard           0.135135135 0.317073171 0.37647059 0.31707317 0.33734940
## Spanning Trees    1.933476457 0.389137532 0.07416105 0.03627963 0.17441257
## Hamming           0.004140787 0.010766046 0.01325052 0.01076605 0.01159420
## IM                0.013804874 0.008180088 0.01930039 0.01226233 0.01547260
## HIM               0.010191189 0.009560899 0.01655417 0.01153847 0.01367163
## alpha=0.5,order=5 0.008491935 0.020301784 0.02406567 0.02037418 0.02199576
## alpha=0.5,order=3 0.005509050 0.013832258 0.01676767 0.01384237 0.01490414
## alpha=0.9,order=3 0.004603432 0.011811179 0.01445525 0.01181188 0.01271483
## ST norm           1.000000000 0.192150121 0.03706354 0.01813783 0.08698589
## f(l)=exp(-0.1l)   0.044250919 0.061886243 0.07166751 0.07888252 0.06898466
## f(l)=exp(-0.4l)   0.177003678 0.247544973 0.28667003 0.31553009 0.27593866
## f(l)=exp(-0.9l)   0.398258275 0.556976189 0.64500757 0.70994271 0.62086198
## f(l)=exp(-1.2l)   0.531011034 0.742634918 0.86001009 0.94659028 0.82781597
## f(l)=exp(-3l)     1.327527584 1.856587295 2.15002522 2.36647571 2.06953992
## f(l)= l. 1(l<2)   0.348768708 0.542333228 0.60509384 2.87885007 2.86265505
##                            X6          X7          X8          X9
## Hamming1          0.010351967 0.008695652 0.004968944 0.004968944
## Jaccard           0.308641975 0.265822785 0.160000000 0.160000000
## Spanning Trees    0.177627834 0.789905360 0.306035432 0.544181137
## Hamming           0.010351967 0.008695652 0.004968944 0.004968944
## IM                0.008225877 0.012216776 0.011883477 0.007761208
## HIM               0.009349553 0.010603395 0.009107893 0.006516393
## alpha=0.5,order=5 0.020066964 0.015946328 0.009236692 0.009433489
## alpha=0.5,order=3 0.013448077 0.011047820 0.006348427 0.006396516
## alpha=0.9,order=3 0.011404211 0.009500644 0.005440566 0.005454620
## ST norm           0.088581133 0.375622018 0.151834523 0.265569039
## f(l)=exp(-0.1l)   0.088203825 0.065197124 0.068367609 0.089362177
## f(l)=exp(-0.4l)   0.352815300 0.260788498 0.273470436 0.357448709
## f(l)=exp(-0.9l)   0.793834426 0.586774120 0.615308481 0.804259595
## f(l)=exp(-1.2l)   1.058445901 0.782365494 0.820411308 1.072346127
## f(l)=exp(-3l)     2.646114754 1.955913735 2.051028271 2.680865318
## f(l)= l. 1(l<2)   2.116852857 2.075781886 0.630429299 2.860846153
##                           X10         X11         X12         X13
## Hamming1          0.004140787 0.004968944 0.005797101 0.007453416
## Jaccard           0.135135135 0.160000000 0.184210526 0.230769231
## Spanning Trees    0.458492191 0.293315928 0.351036517 0.278868638
## Hamming           0.004140787 0.004968944 0.005797101 0.007453416
## IM                0.003625213 0.003379369 0.004831260 0.013501950
## HIM               0.003891548 0.004249149 0.005336078 0.010905413
## alpha=0.5,order=5 0.008017100 0.009401257 0.010680229 0.013868945
## alpha=0.5,order=3 0.005371175 0.006386070 0.007374260 0.009528335
## alpha=0.9,order=3 0.004557969 0.005450977 0.006336050 0.008163017
## ST norm           0.225312842 0.145615465 0.173737818 0.138537667
## f(l)=exp(-0.1l)   0.086621500 0.035167297 0.060078517 0.062082101
## f(l)=exp(-0.4l)   0.346485999 0.140669187 0.240314069 0.248328405
## f(l)=exp(-0.9l)   0.779593498 0.316505670 0.540706654 0.558738911
## f(l)=exp(-1.2l)   1.039457997 0.422007560 0.720942206 0.744985215
## f(l)=exp(-3l)     2.598644993 1.055018900 1.802355514 1.862463038
## f(l)= l. 1(l<2)   2.082257314 2.022185945 2.079880931 2.066424401
##                           X14        X15        X16         X17
## Hamming1          0.010766046 0.01407867 0.01159420 0.007453416
## Jaccard           0.317073171 0.39534884 0.33734940 0.230769231
## Spanning Trees    0.326982980 0.22619909 0.76628242 0.096604564
## Hamming           0.010766046 0.01407867 0.01159420 0.007453416
## IM                0.009825273 0.01362282 0.01374714 0.011240003
## HIM               0.010306399 0.01385262 0.01271631 0.009536537
## alpha=0.5,order=5 0.020156643 0.02564950 0.02045919 0.013077777
## alpha=0.5,order=3 0.013780386 0.01782936 0.01449249 0.009296575
## alpha=0.9,order=3 0.011790383 0.01535934 0.01258662 0.008085259
## ST norm           0.162050218 0.11261976 0.36543232 0.048264752
## f(l)=exp(-0.1l)   0.066136168 0.06540890 0.08236081 0.072415410
## f(l)=exp(-0.4l)   0.264544673 0.26163561 0.32944325 0.289661640
## f(l)=exp(-0.9l)   0.595225514 0.58868012 0.74124732 0.651738690
## f(l)=exp(-1.2l)   0.793634018 0.78490683 0.98832976 0.868984920
## f(l)=exp(-3l)     1.984085046 1.96226707 2.47082439 2.172462299
## f(l)= l. 1(l<2)   0.564566517 2.03022501 2.04400085 0.667207523
##                           X18         X19        X20
## Hamming1          0.005797101 0.004968944 0.01076605
## Jaccard           0.184210526 0.160000000 0.31707317
## Spanning Trees    0.569389208 0.071323192 1.17378979
## Hamming           0.005797101 0.004968944 0.01076605
## IM                0.009037550 0.008160755 0.01844279
## HIM               0.007592223 0.006756047 0.01510040
## alpha=0.5,order=5 0.010072128 0.009740999 0.02130471
## alpha=0.5,order=3 0.007199456 0.006477187 0.01408779
## alpha=0.9,order=3 0.006277853 0.005480022 0.01188869
## ST norm           0.277244452 0.035646486 0.52765871
## f(l)=exp(-0.1l)   0.046987468 0.056083186 0.08135177
## f(l)=exp(-0.4l)   0.187949870 0.224332743 0.32540707
## f(l)=exp(-0.9l)   0.422887208 0.504748672 0.73216590
## f(l)=exp(-1.2l)   0.563849611 0.672998230 0.97622120
## f(l)=exp(-3l)     1.409624028 1.682495575 2.44055300
## f(l)= l. 1(l<2)   2.803882602 2.826417687 2.89605068
change_pointIsland=test_change_point_realistic(N=70,m=c(10,20),p_mod=c(0.6,0.2),p_disp=c(0.1,0.2),p_creation=c(0.0,0.0),opts=2, T=21,verbose=TRUE,m_disp=c(0,0,0),m_creation=c(2,5,0),go_plot=TRUE,initial_message=TRUE,very_verbose=FALSE,save_graph_seq=FALSE,name_file_ext="")
## [1] "Investigating the ability of the distance to detect dynamic regime changes"
## [1] "A graph with N= 70 nodes is considered as per creation model  2"
## [1] "At time t=10, the number of randomly reassigned edges changes from 10  to  20 with new change proba=  NA  vs  0.5 and deletion 0.2"
## [1] "Type of graph generated:  Island"
## [1] "island graph: islands.n= 3 9"

## [1] "time:  1"
## [1] "time:  2"
## [1] "time:  3"
## [1] "time:  4"
## [1] "time:  5"
## [1] "time:  6"
## [1] "time:  7"
## [1] "time:  8"
## [1] "time:  9"
## [1] "time:  10"
## [1] "time:  11"
## [1] "time:  12"
## [1] "time:  13"
## [1] "time:  14"
## [1] "changed back"
## [1] "time:  15"
## [1] "changed back"
## [1] "time:  16"
## [1] "changed back"
## [1] "time:  17"
## [1] "changed back"
## [1] "time:  18"
## [1] "changed back"
## [1] "time:  19"
## [1] "changed back"
## [1] "time:  20"
## [1] "changed back"

print(change_pointIsland$dist)
##                            X1          X2          X3         X4
## Hamming1          0.004140787 0.008281573 0.009109731 0.01035197
## Jaccard           0.196078431 0.357142857 0.385964912 0.43103448
## Spanning Trees    0.023720123 0.011968897 0.015753842 0.03493023
## Hamming           0.028490028 0.056980057 0.062678063 0.07122507
## IM                0.015677653 0.017482126 0.013241144 0.03365501
## HIM               0.022994244 0.042144701 0.045298275 0.05570310
## alpha=0.5,order=5 0.076854645 0.168190424 0.199503855 0.21960687
## alpha=0.5,order=3 0.046976091 0.099086311 0.114060091 0.12765457
## alpha=0.9,order=3 0.035066471 0.071779669 0.080557839 0.09124682
## ST norm           0.011859505 0.005984377 0.007876758 0.01746334
## f(l)=exp(-0.1l)   0.047436662 0.059548815 0.081064100 0.07365962
## f(l)=exp(-0.4l)   0.189746647 0.238195261 0.324256398 0.29463849
## f(l)=exp(-0.9l)   0.426929955 0.535939338 0.729576896 0.66293660
## f(l)=exp(-1.2l)   0.569239940 0.714585784 0.972769195 0.88391546
## f(l)=exp(-3l)     1.423099850 1.786464460 2.431922987 2.20978865
## f(l)= l. 1(l<2)   2.011299636 0.346948732 1.955581560 2.81008300
##                            X5          X6          X7          X8
## Hamming1          0.008695652 0.006625259 0.006625259 0.009109731
## Jaccard           0.375000000 0.296296296 0.296296296 0.385964912
## Spanning Trees    0.046646257 0.033386015 0.005657548 0.042653546
## Hamming           0.059829060 0.045584046 0.045584046 0.062678063
## IM                0.026218076 0.025905694 0.028441509 0.010320229
## HIM               0.046189306 0.037074319 0.037992267 0.044916849
## alpha=0.5,order=5 0.183940156 0.147361000 0.158849681 0.204443371
## alpha=0.5,order=3 0.107017177 0.083869860 0.087900336 0.116039551
## alpha=0.9,order=3 0.076510974 0.058806283 0.059838146 0.080995043
## ST norm           0.023318901 0.016691457 0.002828766 0.021323540
## f(l)=exp(-0.1l)   0.060803996 0.060271004 0.054164812 0.075353449
## f(l)=exp(-0.4l)   0.243215983 0.241084016 0.216659249 0.301413797
## f(l)=exp(-0.9l)   0.547235962 0.542439036 0.487483311 0.678181043
## f(l)=exp(-1.2l)   0.729647949 0.723252048 0.649977748 0.904241390
## f(l)=exp(-3l)     1.824119874 1.808130120 1.624944371 2.260603476
## f(l)= l. 1(l<2)   2.031319401 0.415644422 0.365271996 0.586877310
##                            X9         X10         X11         X12
## Hamming1          0.009109731 0.005797101 0.003312629 0.004140787
## Jaccard           0.385964912 0.264150943 0.160000000 0.196078431
## Spanning Trees    0.016178508 0.025074965 0.004761438 0.025241222
## Hamming           0.062678063 0.039886040 0.022792023 0.028490028
## IM                0.014662235 0.016140329 0.012458056 0.022481487
## HIM               0.045516594 0.030425371 0.018366811 0.025662219
## alpha=0.5,order=5 0.196364603 0.122426314 0.067707287 0.093077097
## alpha=0.5,order=3 0.113174655 0.071040443 0.039793977 0.052768337
## alpha=0.9,order=3 0.080386719 0.050849392 0.028782201 0.036960271
## ST norm           0.008089077 0.012536825 0.002380715 0.012619941
## f(l)=exp(-0.1l)   0.081822738 0.056468835 0.051699798 0.083400190
## f(l)=exp(-0.4l)   0.327290953 0.225875339 0.206799190 0.333600761
## f(l)=exp(-0.9l)   0.736404645 0.508219513 0.465298178 0.750601711
## f(l)=exp(-1.2l)   0.981872860 0.677626017 0.620397570 1.000802282
## f(l)=exp(-3l)     2.454682149 1.694065043 1.550993925 2.502005705
## f(l)= l. 1(l<2)   2.070980953 2.800048069 2.006878022 1.857028168
##                           X13         X14         X15         X16
## Hamming1          0.007867495 0.007039337 0.008281573 0.009109731
## Jaccard           0.345454545 0.314814815 0.357142857 0.385964912
## Spanning Trees    0.039850764 0.028816444 0.024940236 0.038488308
## Hamming           0.054131054 0.048433048 0.056980057 0.062678063
## IM                0.025208525 0.012845977 0.008995062 0.014430383
## HIM               0.042223458 0.035431478 0.040789938 0.045479531
## alpha=0.5,order=5 0.165695815 0.157520686 0.173194938 0.182986847
## alpha=0.5,order=3 0.096554800 0.089498991 0.101001251 0.108381213
## alpha=0.9,order=3 0.069184891 0.062691712 0.072504624 0.078705371
## ST norm           0.019922745 0.014407225 0.012469471 0.019241779
## f(l)=exp(-0.1l)   0.069071732 0.045181096 0.077410863 0.078145135
## f(l)=exp(-0.4l)   0.276286930 0.180724385 0.309643452 0.312580539
## f(l)=exp(-0.9l)   0.621645591 0.406629865 0.696697767 0.703306214
## f(l)=exp(-1.2l)   0.828860789 0.542173154 0.928930357 0.937741618
## f(l)=exp(-3l)     2.072151971 1.355432885 2.322325891 2.344354045
## f(l)= l. 1(l<2)   2.807413365 2.026569518 1.970520917 2.785752341
##                           X17        X18        X19        X20
## Hamming1          0.009523810 0.01035197 0.01076605 0.01242236
## Jaccard           0.403508772 0.43103448 0.44067797 0.49180328
## Spanning Trees    0.017228769 0.02230572 0.03583636 0.02573272
## Hamming           0.065527066 0.07122507 0.07407407 0.08547009
## IM                0.021373339 0.01223297 0.03432348 0.01666912
## HIM               0.048737131 0.05110116 0.05772811 0.06157514
## alpha=0.5,order=5 0.189642619 0.22270737 0.24738816 0.30210876
## alpha=0.5,order=3 0.112712218 0.12852760 0.13927214 0.16690796
## alpha=0.9,order=3 0.081967711 0.09128036 0.09638414 0.11321382
## ST norm           0.008614171 0.01115240 0.01791626 0.01286565
## f(l)=exp(-0.1l)   0.076261383 0.06703653 0.09508799 0.09478136
## f(l)=exp(-0.4l)   0.305045533 0.26814614 0.38035197 0.37912546
## f(l)=exp(-0.9l)   0.686352450 0.60332881 0.85579194 0.85303228
## f(l)=exp(-1.2l)   0.915136600 0.80443841 1.14105591 1.13737637
## f(l)=exp(-3l)     2.287841499 2.01109603 2.85263979 2.84344093
## f(l)= l. 1(l<2)   0.443444301 3.35667095 2.76225224 2.04366639
change_pointSBM=test_change_point_realistic(N=70,m=c(10,20),p_mod=c(0.6,0.2),p_disp=c(0.1,0.2),p_creation=c(0.0,0.0),opts=4, T=21,verbose=TRUE,m_disp=c(0,0,0),m_creation=c(2,5,0),go_plot=TRUE,initial_message=TRUE,very_verbose=FALSE,save_graph_seq=FALSE,name_file_ext="",block.sizes=c(24,23,23))
## [1] "Investigating the ability of the distance to detect dynamic regime changes"
## [1] "A graph with N= 70 nodes is considered as per creation model  4"
## [1] "At time t=10, the number of randomly reassigned edges changes from 10  to  20 with new change proba=  NA  vs  0.5 and deletion 0.2"
## [1] "Type of graph generated:  SBM"
## [1] 70
## [1] "stochastic block model: block size c" 
## [2] "stochastic block model: block size 24"
## [3] "stochastic block model: block size 23"
## [4] "stochastic block model: block size 23"

## [1] "time:  1"
## [1] "time:  2"
## [1] "time:  3"
## [1] "time:  4"
## [1] "time:  5"
## [1] "time:  6"
## [1] "time:  7"
## [1] "time:  8"
## [1] "time:  9"
## [1] "time:  10"
## [1] "time:  11"
## [1] "time:  12"
## [1] "time:  13"
## [1] "time:  14"
## [1] "changed back"
## [1] "time:  15"
## [1] "changed back"
## [1] "time:  16"
## [1] "changed back"
## [1] "time:  17"
## [1] "changed back"
## [1] "time:  18"
## [1] "changed back"
## [1] "time:  19"
## [1] "changed back"
## [1] "time:  20"
## [1] "changed back"

print(change_pointSBM$dist)
##                            X1          X2          X3           X4
## Hamming1          0.006625259 0.009109731 0.009109731 0.0115942029
## Jaccard           0.042780749 0.058355438 0.058355438 0.0736842105
## Spanning Trees    0.003773863 0.002897952 0.002651941 0.0015402461
## Hamming           0.006625259 0.009109731 0.009109731 0.0115942029
## IM                0.003407119 0.003094169 0.004916351 0.0044353955
## HIM               0.005267946 0.006802980 0.007319757 0.0087777638
## alpha=0.5,order=5 0.027445088 0.034379880 0.033864426 0.0419430275
## alpha=0.5,order=3 0.012142279 0.015907315 0.015764756 0.0197872360
## alpha=0.9,order=3 0.007969894 0.010860213 0.010902581 0.0138585531
## ST norm           0.001886929 0.001448975 0.001325970 0.0007701229
## f(l)=exp(-0.1l)   0.069604652 0.070897597 0.060262552 0.0485432981
## f(l)=exp(-0.4l)   0.278418607 0.283590386 0.241050210 0.1941731925
## f(l)=exp(-0.9l)   0.626441866 0.638078369 0.542362972 0.4368896831
## f(l)=exp(-1.2l)   0.835255821 0.850771159 0.723150629 0.5825195775
## f(l)=exp(-3l)     2.088139554 2.126927898 1.807876573 1.4562989438
## f(l)= l. 1(l<2)   2.775524755 1.979408515 0.353463424 0.2956737278
##                             X5           X6          X7           X8
## Hamming1          0.0082815735 0.0082815735 0.009937888 0.0057971014
## Jaccard           0.0531914894 0.0531914894 0.063492063 0.0375335121
## Spanning Trees    0.0005556334 0.0009161044 0.003332786 0.0011290947
## Hamming           0.0082815735 0.0082815735 0.009937888 0.0057971014
## IM                0.0027804311 0.0042577739 0.005973828 0.0043710560
## HIM               0.0061771861 0.0065845690 0.008199032 0.0051338346
## alpha=0.5,order=5 0.0302341641 0.0329608333 0.039569455 0.0191682035
## alpha=0.5,order=3 0.0142043087 0.0148630420 0.017837219 0.0094668975
## alpha=0.9,order=3 0.0098787180 0.0099852326 0.011944823 0.0068435543
## ST norm           0.0002778167 0.0004580522 0.001666392 0.0005645473
## f(l)=exp(-0.1l)   0.0599597777 0.0568603638 0.073897504 0.0542948691
## f(l)=exp(-0.4l)   0.2398391108 0.2274414552 0.295590017 0.2171794766
## f(l)=exp(-0.9l)   0.5396379994 0.5117432743 0.665077539 0.4886538223
## f(l)=exp(-1.2l)   0.7195173325 0.6823243657 0.886770052 0.6515384297
## f(l)=exp(-3l)     1.7987933313 1.7058109144 2.216925130 1.6288460742
## f(l)= l. 1(l<2)   2.7982308992 2.8006185181 1.954404988 1.9441906421
##                             X9          X10          X11          X12
## Hamming1          0.0041407867 7.453416e-03 0.0074534161 0.0057971014
## Jaccard           0.0269541779 4.800000e-02 0.0480000000 0.0375335121
## Spanning Trees    0.0018452749 1.209343e-04 0.0014172311 0.0014226261
## Hamming           0.0041407867 7.453416e-03 0.0074534161 0.0057971014
## IM                0.0020952487 1.984889e-03 0.0020324445 0.0039965983
## HIM               0.0032814770 5.454044e-03 0.0054627943 0.0049789147
## alpha=0.5,order=5 0.0149381685 2.788794e-02 0.0288150585 0.0219510276
## alpha=0.5,order=3 0.0070696447 1.292854e-02 0.0131625916 0.0101366885
## alpha=0.9,order=3 0.0049253223 8.919444e-03 0.0089588265 0.0069681144
## ST norm           0.0009226372 6.046714e-05 0.0007086154 0.0007113129
## f(l)=exp(-0.1l)   0.0532724022 5.060076e-02 0.0599142934 0.0563395659
## f(l)=exp(-0.4l)   0.2130896086 2.024030e-01 0.2396571736 0.2253582636
## f(l)=exp(-0.9l)   0.4794516194 4.554069e-01 0.5392286406 0.5070560931
## f(l)=exp(-1.2l)   0.6392688259 6.072091e-01 0.7189715208 0.6760747908
## f(l)=exp(-3l)     1.5981720648 1.518023e+00 1.7974288020 1.6901869770
## f(l)= l. 1(l<2)   2.0139122650 2.807501e+00 3.4023297563 2.0207248654
##                            X13          X14          X15          X16
## Hamming1          0.0049689441 0.0082815735 0.0107660455 0.0091097308
## Jaccard           0.0322580645 0.0531914894 0.0686015831 0.0583554377
## Spanning Trees    0.0008121710 0.0014859326 0.0005886513 0.0001340042
## Hamming           0.0049689441 0.0082815735 0.0107660455 0.0091097308
## IM                0.0032272644 0.0039200080 0.0046539220 0.0048679948
## HIM               0.0041896086 0.0064788472 0.0082935736 0.0073035803
## alpha=0.5,order=5 0.0181784032 0.0292194601 0.0381645860 0.0356546394
## alpha=0.5,order=3 0.0085408924 0.0139693769 0.0182034379 0.0161820285
## alpha=0.9,order=3 0.0059318266 0.0098553573 0.0128103612 0.0109543077
## ST norm           0.0004060855 0.0007429662 0.0002943256 0.0000670021
## f(l)=exp(-0.1l)   0.0411606289 0.0615725086 0.0624621484 0.0558548095
## f(l)=exp(-0.4l)   0.1646425156 0.2462900345 0.2498485936 0.2234192380
## f(l)=exp(-0.9l)   0.3704456601 0.5541525776 0.5621593355 0.5026932854
## f(l)=exp(-1.2l)   0.4939275468 0.7388701034 0.7495457807 0.6702577139
## f(l)=exp(-3l)     1.2348188671 1.8471752585 1.8738644517 1.6756442847
## f(l)= l. 1(l<2)   2.0093477553 0.3224456918 0.2991573451 0.3582929445
##                            X17          X18          X19          X20
## Hamming1          0.0091097308 0.0091097308 1.159420e-02 0.0107660455
## Jaccard           0.0583554377 0.0583554377 7.368421e-02 0.0686015831
## Spanning Trees    0.0001383218 0.0011007879 5.928691e-05 0.0006055407
## Hamming           0.0091097308 0.0091097308 1.159420e-02 0.0107660455
## IM                0.0037573259 0.0065605836 4.364339e-03 0.0046003762
## HIM               0.0069679514 0.0079381501 8.759937e-03 0.0082786230
## alpha=0.5,order=5 0.0360054243 0.0350876440 4.710455e-02 0.0402817432
## alpha=0.5,order=3 0.0162778317 0.0160384310 2.098832e-02 0.0186907747
## alpha=0.9,order=3 0.0110068716 0.0108995581 1.396127e-02 0.0128492406
## ST norm           0.0000691609 0.0005503939 2.964346e-05 0.0003027703
## f(l)=exp(-0.1l)   0.0599860476 0.0619665270 6.958717e-02 0.0660356656
## f(l)=exp(-0.4l)   0.2399441903 0.2478661079 2.783487e-01 0.2641426624
## f(l)=exp(-0.9l)   0.5398744282 0.5576987427 6.262845e-01 0.5943209903
## f(l)=exp(-1.2l)   0.7198325709 0.7435983237 8.350460e-01 0.7924279871
## f(l)=exp(-3l)     1.7995814272 1.8589958092 2.087615e+00 1.9810699677
## f(l)= l. 1(l<2)   1.9876725281 1.9915018221 2.396268e-01 0.3341224608

IV. Compare ability to recognize classes of graphs

Here we brefly compare the different distances’ ability to distinguish graphs that exhibit different topological properties. We generate 6 E-R graphs on 60 nodes, 6 Power law graphs, 6 island graphs, as well as 6 SBM networks. We compute the pairwise distances between the different graphs. If all goes well, the distance should cluster the different topologies together, and the heatmap should exhibit a block diagonal structure.

N=60
K=6
A<-vector("list",4*K)
args<-list(p=0.1,power=1.4,islands.n=3,islands.size=20,islands.pin=0.3,n.inter=3,K=6,block.sizes=c(20,20,20),pm=cbind( c(.4,0.1, .001), c(.1,0.2, .01),c(.001,0.01, .5)))
verbose=FALSE

for (i in 1:10){
  A[[i]]<-generate_random_adjacency(N,p[1], TRUE)
  A[[i+K]]<-generate_realistic_adjacency(N,opts=1, verbose=verbose)
  A[[i+K]]=as(get.adjacency(A[[i+K]]),"matrix")
  A[[i+2*K]]<-generate_realistic_adjacency(N,opts=2, verbose=verbose,islands.n=3,islands.size=20)
  A[[i+2*K]]=as(get.adjacency(A[[i+2*K]]),"matrix")
  A[[i+3*K]]<-generate_realistic_adjacency(N,opts=4, verbose=verbose,block.sizes=c(20,20,20))
  A[[i+3*K]]=as(get.adjacency(A[[i+3*K]]),"matrix")
}

print("generated")
## [1] "generated"
distances<-vector("list",8)
for (k in 1:8){
  distances[[k]]=matrix(0,4*K,4*K)
}
for (j in 2:(4*K)){
  for (i in 1:(j-1)){
    
    sp_Anew=get_number_spanning_trees(A[[i]])
    sp_A=get_number_spanning_trees(A[[j]])
    distances[[2]][i,j]=abs(log(max(sp_A,1))-log(max(1,sp_Anew)))
    distances[[1]][i,j]<-jaccard_based_distance(A[[i]], A[[j]])
    temp<-netdist(A[[i]], A[[j]],d = "HIM")
    distances[[3]][i,j]=temp[1]
    distances[[4]][i,j]=temp[2]
    distances[[5]][i,j]=temp[3]
    distances[[6]][i,j]<-poly_distance(A[[i]], A[[j]],order_max=3,alpha=0.5)
    distances[[7]][i,j]<-eigen_distance(A[[i]], A[[j]],function(x){return(-1.2*x)},p=2)
    distances[[8]][i,j]<-eigen_distance(A[[i]], A[[j]],function(x){ifelse(x<2,x,0)})
  }
}

for (k in 1:8){
  distances[[k]]=distances[[k]]+t(distances[[k]])
  heatmap.2(distances[[k]],dendrogram='none', Rowv=FALSE, Colv=FALSE,trace='none')
}